#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//1视为两段0的叠加，拆分开得到若干段，k = 各段长度的最大公因数

int main()
{
    int t = 0;
    scanf("%d", &t);
    while(t--)
    {
        int n = 0;
        scanf("%d", &n);
        char str[n + 1];
        scanf("%s", str);

        //不考虑边界1
        int pre = 0;
        int aft = n - 1;
        while(str[pre] == '1'){pre++;}
        while(str[aft] == '1'){aft--;}

        int k = 0;
        int ret[n + 1];//各段长度
        memset(ret, 0, sizeof(ret));

        int flag = 0;
        int count1 = 0;
        int count2 = 0;
        for(int i = pre; i <= aft; i++)
        {
            if(str[i] == '0')
            {
                flag = 1;
            }

            if(flag == 1)
            {
                if(str[i] == '0')
                count1++;
                if(str[i] == '1')
                count2++;

                if(str[i] == '1' && str[i + 1] != '1')
                {
                    flag = 0;
                    ret[k] = count1 + count2;
                    k++;
                    ret[k] = count2;
                    while(str[i + 1] == '0' && count1--)
                    {
                        ret[k]++;
                        i++;
                    }
                    k++;

                    count1 = count2 = 0;
                }
            }
        }
        ret[k] = count1;

        int min1 = ret[0];//第一小
        int min2 = ret[0];//第二小
        for(int i = 1; i <= k; i++)
        {
            if(ret[i] < min1)
            {
                min2 = min1;
                min1 = ret[i];
            }
            else if(ret[i] < min2)
            {
                min2 = ret[i];
            }
        }

        //各段长度的最大公因数
        while(min1 != 0)
        {
            int tmp = min2 % min1;
            min2 = min1;
            min1 = tmp;
        }

        if(min2 != 0)
        printf("%d\n", min2);
        else
        printf("%d\n", n);
    }
    return 0;
}